package medium;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/8/13 19:33
 */
public class No22_括号生成 {
    public static void main(String[] args) {
        Solution22 solution22 = new Solution22();
        List<String> res = solution22.generateParenthesis(3);
        System.out.println();
    }
}

class Solution22 {
    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        // n = 1 ()
        // n = 2 () (()) ()()
        //动态规划
        //定义第一个索引从1开始,方便大家理解
        List<String>[] dp = new List[n + 1];
        //用于add结果去重
        Set<String> set = new HashSet<>();

        //当索引为1时
        //定义dp[n]为 n对括号时候的所有有效括号组合
        dp[1] = new ArrayList<>();
        dp[1].add("()");
        //开始计算2-n的结果
        for (int i = 2; i <= n; i++) {
            dp[i] = new ArrayList<>();
            //获取上一级的dp的所有括号组合
            for (int j = 0; j < dp[i - 1].size(); j++) {
                //定义base为上一级的dp的每一个元素
                String base = dp[i - 1].get(j);
                //对base进行遍历
                for (int k = 0; k < base.length(); k++) {
                    //获取左右部分
                    String left = base.substring(0, k);
                    String right = base.substring(k);
                    String add = left + "()" + right;
                    //处理值
                    if (set.add(add)) {
                        //当前dp可以加
                        dp[i].add(add);
                    }
                }
            }
        }
        return dp[n];
    }
}



    //List<String> res = new ArrayList<>();
    //public List<String> generateParenthesis(int n) {
    //    if (n == 0) {
    //        return res;
    //    }
    //    //二叉树? 二叉树想到递归
    //    //开始:先递归"(" 再递归")"
    //    generateParenthesis("", 0, 0, n);
    //    return res;
    //}
    //
    ////add:遍历过程中的值
    ////zuoKuo:add中左括号的个数
    ////youKuo:add中右括号的个数
    //public void generateParenthesis(String add,int zuoKuo,int youKuo,int n) {
    //    
    //    //限制无限调用 ((((
    //    if (zuoKuo == n+1 || youKuo == n+1 || zuoKuo < youKuo) {
    //        return;
    //    }
    //
    //    if (zuoKuo == n && youKuo == n) {
    //        res.add(add);
    //        return;
    //    }
    //    
    //    //处理加值问题
    //    
    //    //处理"("
    //    add += "(";
    //    zuoKuo += 1;
    //    //System.out.println(add);//((((
    //    generateParenthesis(add,zuoKuo,youKuo,n);
    //    //注意回溯!!!!
    //    add = add.substring(0, add.length() - 1);
    //    //回溯,左括号没了!!所以..
    //    zuoKuo -= 1;
    //    
    //    
    //    //((((
    //    //(((
    //    //处理")"
    //    add += ")";
    //    youKuo += 1;
    //    //System.out.println(add);
    //    generateParenthesis(add,zuoKuo,youKuo,n);
    //    //这里是否也要回溯?? 确实不用!
    //}



    //public List<String> generateParenthesis(int n) {
    //    //本节算法代入元素众多,增加注释配合debug,帮助大家更快理解
    //    // ()()() "(" ")"
    //    
    //    //啥都想不出来咋办??? 暴力法!!!!
    //    //比如n=3: data[]{1,-1,1,-1,1,-1}
    //    
    //    //根据n生成的数组,存放n对括号每一个字符代表的值
    //    int[] data = new int[2 * n];
    //    for (int i = 0; i < data.length; i++) {
    //        if (i % 2 == 0) {
    //            data[i] = 1;
    //        } else {
    //            data[i] = -1;
    //        } 
    //    }
    //    
    //    //对应值获取括号 1-> "(" -1-> ")"
    //    Map<Integer, String> kuoMap = new HashMap<>();
    //    kuoMap.put(1, "(");
    //    kuoMap.put(-1, ")");
    //    List<String> res = new ArrayList<>();
    //    Set<Integer> indexs = new HashSet<>();
    //    Set<String> set = new HashSet<>();
    //    generateParenthesis(kuoMap, res, "", data, indexs, 0, set);
    //    return res;
    //}
    //
    ////add:遍历的过程中加的 "(",")"
    ////kuoMap存放括号对应值
    ////res:存放计算结果
    ////data: 通过n->生成的括号数组值
    ////indexs: Set<Integer> 存放已经遍历的索引
    ////check: 定义为括号的值和,如果值小于0,则不是有效括号
    ////set: 存放计算结果判断是否重复
    //public void generateParenthesis(Map<Integer, String> kuoMap
    //        , List<String> res, String add, int[] data
    //        ,Set<Integer> indexs,int check
    //        ,Set<String> set) {
    //
    //
    //    if (check < 0) {
    //        return;
    //    }
    //    
    //    //否则,可能可以加
    //    //什么情况下可以加???
    //    if (add.length() == data.length && !set.contains(add)) {
    //        //用于下次判断
    //        set.add(add);
    //        res.add(add);
    //        return;
    //    }
    //    
    //    for (int i = 0; i < data.length; i++) {
    //        if (!indexs.contains(i)) {
    //            //对add进行处理
    //            String kuo = kuoMap.get(data[i]);
    //            add += kuo;
    //            indexs.add(i);
    //            check += data[i];
    //            generateParenthesis(kuoMap, res, add, data, indexs, check,set);
    //            //回溯
    //            //add减去一位
    //            //check也要减
    //            add = add.substring(0, add.length() - 1);
    //            check -= data[i];
    //            indexs.remove(i);
    //        }
    //    }
    //}







